"""
343. 整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""

"""
解法1：

使用动态规划

求n的最大拆分，

还是很难想到为什么要加 i * (n - i)

这是我想到最容易理解的了

用5举例

F(5) = max { F(4)*1, F(3)*2, F(2)*3,F(1)*4, 4*1, 3*2, 2*3, 1*4}
描述： 求5的最大拆分，就是求4的最大拆分和新组成的序列比较

F(4) = max { F(3)*1, F(2)*2,F(1)*3, 3 * 1, 2*1, 1*2}
F(3) = max { F(2)*1, F(1)*2, 2 * 1, 1*2}
F(2) = max { F(1)*1, 1 * 1}
F(1) = 1

就是这样子，我们递归回去

F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 6

"""
from functools import lru_cache


class Solution:
    def integerBreak(self, n: int) -> int:

        @lru_cache(None)
        def helper(n: int):
            print("n=", n)
            if n <= 1:
                return n
            return max([max(helper(n - i) * i, i * (n-i)) for i in range(1, n)])

        return helper(n)


"""
使用数学的解法

要使结果最大，其实就是尽可能的拆成3，如果剩余的数是4，那么保留4
"""


class Solution1:
    def integerBreak(self, n: int) -> int:
        if n == 2:
            return 1
        if n == 3:
            return 2
        ret = 1
        while n > 4:
            ret *= 3
            n -= 3

        return ret * n

"""
另一种递归，使用mem记录结果
"""

class Solution2:
    def integerBreak(self, n: int) -> int:
        mem = [-1] * (n+1)

        def backtrack(n: int):

            if n== 1:
                return 1

            if mem[n] != -1:
                return mem[n]

            res = -1
            for i in range(1, n):
                print(res, i*(n-i))
                res = max(res, i*(n-i), i* backtrack(n-i))
            mem[n] = res
            return res

        ans = backtrack(n)
        return ans
"""
动态规划
"""

class Solution3:
    def integerBreak(self, n: int) -> int:
        dp = [1] * (n + 1)

        for i in range(2, n+1):
            for j in range(1, i):
                dp[i] = max(j * (i-j) , j * dp[i-j], dp[i])
        return dp[-1]



def test():
    r = Solution().integerBreak(2)
    assert r == 1

def test3():
    r = Solution().integerBreak(3)
    assert r == 2


def test5():
    r = Solution().integerBreak(5)
    assert r == 6

def test6():
    r = Solution().integerBreak(6)
    assert r == 9

def test7():
    r = Solution().integerBreak(7)
    assert r == 12

def test8():
    r = Solution().integerBreak(8)
    assert r == 18

def test9():
    r = Solution().integerBreak(9)
    assert r == 27
def test10():
    r = Solution().integerBreak(10)
    assert r == 36


if __name__ == "__main__":
    r = Solution2().integerBreak(5)
    print(r)
